#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
# @Time    : 2021/3/14 13:47
# @Author  : cs
# @File    : 7.8.py
# @Software: PyCharm
class Empty(Exception):
    pass


class DoublyLinkedBase:
    """A base class providing a doubly linked list representation."""

    class _Node:
        """Lightweight,nonpublic class for storing a doubly linked node."""
        __slots__ = "_element", "_prev", "_next"  # streaming memory

        def __init__(self, element, prev, next):  # initialize node's fields
            self._element = element  # use's element
            self._prev = prev  # previous node rederence
            self._next = next  # next node reference

    def __init__(self):
        """Create an empty list."""
        self._header = self._Node(None, None, None)
        self._tailer = self._Node(None, None, None)
        self._header._next = self._tailer  # trailer is after header
        self._tailer._prev = self._header  # header is before trailer
        self._size = 0  # number of elements

    def __len__(self):
        """Return the number of elements in the list."""
        return self._size

    def is_empty(self):
        """Return True if list is empty."""
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):
        """Add element e between two existing nodes and return new node."""
        newest = self._Node(e, predecessor, successor)
        predecessor._next = newest
        successor._prev = newest
        self._size += 1
        return newest

    def _delete_node(self, node):
        """Delete nonsentinel node from the list and return its element."""
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        element = node._element  # record deleted element
        node._prev = node._next = node._element = None  # deprecate node
        return element

    def enqueue(self, item):
        if self._size == 0:
            self._insert_between(item, self._header, self._tailer)
        else:
            self._insert_between(item, self._tailer._prev, self._tailer)
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("the doublelinked is None!")
        return self._delete_node(self._header._next)

    def midnode(self):
        walk1 = self._header._next
        walk2 = self._tailer._prev
        node = None
        if self._header._next == self._tailer._prev:
            return self._header._next._element
        elif self.is_empty():
            return None
        while  walk1._next is not None and walk2._prev is not None:
            node = walk1
            walk1 = walk1._next
            walk2 = walk2._prev
            if walk1 == walk2:
                return node._element
            if walk1._next == walk2:
                return walk1._next._element
if __name__ == "__main__":
    doubleLink = DoublyLinkedBase()
    [doubleLink.enqueue(i) for i in range(10)]
    print(doubleLink.midnode())
    # [print(doubleLink.dequeue()) for i in range(10)]

